package com.example.demo.zaqizabatest;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 一个数组nums，一个数组values，每次只能从nums头或尾取，
 * 假设第i次取得值是x，价值=x*values[i-1]，求怎么取得总价值最大？
 * @author lys4134
 * @ClassName Solution
 * @Date 2022/03/21 10:44:48
 * @Description Solution
 * @Version 1.0
 **/
public class Solution {

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param nums   int整型一维数组
     * @param values int整型一维数组
     * @return int整型
     */
    public static int getMaxValue(int[] nums, int[] values) {
        // write code here
        int numsLength = nums.length;
        int valuesLength = values.length;
        if (numsLength == 0 || valuesLength == 0 || numsLength > valuesLength) {
            return 0;
        }

        TreeNode root = new TreeNode(null, 0, numsLength - 1, 0, 0);
        generatorTree(nums, values, root, 0);
//        List<Integer> maxValues = new ArrayList<>(2 ^ numsLength);
        List<Integer> maxValues = new LinkedList<>();
        print(root, maxValues);
        int maxValue = 0;
        for (Integer item : maxValues) {
            if (item > maxValue) {
                maxValue = item;
            }
        }
        return maxValue;
    }

    public static void print(TreeNode root, List<Integer> maxValues) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            maxValues.add(root.values);
            return;
        }
        print(root.left, maxValues);
        print(root.right, maxValues);

    }

    public static void generatorTree(int[] nums, int[] values, TreeNode root, int count) {
        count++;
        if (root.leftIndex >= nums.length || root.rightIndex < 0 || count > nums.length) {
            return;
        }
        TreeNode leftTemp = new TreeNode(root, root.leftIndex + 1, root.rightIndex, count,
                root.values + values[count - 1] * nums[root.leftIndex]);
        TreeNode rightTemp = new TreeNode(root, root.leftIndex, root.rightIndex - 1, count,
                root.values + values[count - 1] * nums[root.rightIndex]);
        root.left = leftTemp;
        root.right = rightTemp;
        generatorTree(nums, values, leftTemp, count);
        generatorTree(nums, values, rightTemp, count);

    }

    static class TreeNode {
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
        public int leftIndex;
        public int rightIndex;
        public int count;
        public int values;

        public TreeNode(TreeNode parent, int leftIndex, int rightIndex, int count, int values) {
            this.parent = parent;
            this.leftIndex = leftIndex;
            this.rightIndex = rightIndex;
            this.count = count;
            this.values = values;
        }

        @Override
        public String toString() {
            return "{" +
                    "leftIndex=" + leftIndex +
                    ", rightIndex=" + rightIndex +
                    ", count=" + count +
                    ", values=" + values +
                    '}';
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 5, 6, 8, 2, 7, 8, 9, 0};
        int[] values = new int[]{7, 8, 9, 6, 1, 2, 3, 5, 4};
        System.out.println(getMaxValue(nums, values));
    }
}
